package io.zouyalong.algo.leetcode;

/**
 * https://leetcode-cn.com/problems/house-robber/
 */
public class HouseRobber {
    public static void main(String[] args) {
        var input = new int[]{1,2,3,1};
        System.out.printf("out: %d", HouseRobber.dp(input));
    }
    public static int dp(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] results = new int[nums.length+1];
        results[0] = 0;
        results[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            int rob = nums[i-1] + results[i-2];
            int notRob = results[i-1];
            results[i] = Math.max(rob, notRob);
        }
        return results[results.length-1];
    }
}
